package 力扣.双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 四数之和 {


    //四树之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
       Arrays.sort(nums);
       return nSum(nums,4,0,target);
    }
    //n树之和
    public List<List<Integer>> nSum(int[] nums,int n,int start,int target){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int len=nums.length;
        if (n<2 || len<n){
            return res;
        }
        if (n==2){
            int lo=start;
            int hi=len-1;
            while (lo<hi){
                List<Integer> list = new ArrayList<>();
                int sum=nums[lo]+nums[hi];
                int left=nums[lo];
                int right=nums[hi];
                if (sum<target){
                    while (lo<hi && nums[lo]==left)
                        lo++;
                }
                else if (sum>target){
                    while (lo<hi && nums[hi]==right)
                        hi--;
                }
                else {
                     list.add(left);
                     list.add(right);
                     res.add(new ArrayList<>(list));
                     while (lo<hi && nums[lo]==left)
                        lo++;
                     while (lo<hi && nums[hi]==right)
                        hi--;
                }
            }
        }
        //当n大于2时，递归调用（n-1）Sum的结果
        else {
            for (int i = start; i < len; i++) {
                List<List<Integer>> sub = nSum(nums,n-1,i+1,target-nums[i]);
                for (List<Integer> integers : sub) {
                    integers.add(nums[i]);
                    res.add(new ArrayList<>(integers));
                }
                while (i<len-1 && nums[i]==nums[i+1])
                    i++;
            }
        }
      return res;
    }
}
